917 741
129836267 20262326 50217544 667358643 509934175 86621193 365516144 986198942 132271861 291748959 661333839 933676932 376081826 514579992 665568252 364319160 731663292 235765146 423863857 720529873 240241025 666101966 639363020 948957481 208252560 54330785 875299918 29371233 776297581 804535941 57788767 748595931 998306562 237906669 950165320 719822655 546692889 215058900 253925751 685928439 102088419 273797687 125965567 210239666 603367540 147882390 902493461 649439716 725458500 552349815 944444820 872616261 35236271 963460323 986376570 965475406 817815926 413496551 798459753 663072447 278413884 926463253 599935527 383840028 684598026 431545600 92495646 152242475 108459468 422069699 194155228 911669367 437970898 699385979 767790996 884278992 308602448 631893192 164003228 343354569 440446686 663486289 687566317 838926393 216134648 753744957 355050150 786000571 484859775 467571130 809707913 89565741 495264054 418979961 473457789 58941237 621684550 806194736 303215626 875507639 326564026 402789399 349414368 996814688 838138372 960788332 154856272 180816415 842175350 922336239 921518033 778205862 436436938 493617766 54793597 471220973 90285723 554832154 487528849 685935792 483196137 4374104 925641969 383415788 259247001 193969394 656949409 845245798 110451187 698444475 515825741 488005924 791923746 893036815 741886658 482761457 441314744 24504648 791705714 434131677 496053799 422580042 459102197 532657083 254875976 670438904 992827010 822085026 375224280 901922748 552286842 279367789 760828406 855541507 942269918 450603579 466112935 320090303 712429268 134404591 52795731 115501795 145607718 32982448 273424453 797126891 828317634 340286315 9745710 937849425 465116987 621636940 569033378 63316249 2015302 313798217 534148505 628130886 932251454 580340375 99180528 122395234 345667489 531819570 129746662 376135674 766435473 753567066 596220319 899238432 758258516 425515280 538618788 781319912 516633045 935767966 412201313 430781931 906278176 719716108 440940710 12841159 385866217 411751339 527503143 249683356 970286854 687182478 370136828 321000336 472607729 802044428 792657697 232669517 244532551 399976000 118579191 827851646 683978571 904574345 556986306 679673173 841579108 466596618 876905256 190259464 105889690 246518571 547587000 753498703 444493597 550736406 290846305 87532264 625460414 572132923 94795767 75625236 344376436 972907212 937102769 885903895 521831129 911736386 92468653 359346875 12799915 145428694 177450859 103886285 471508555 76215049 408113742 191295135 946495041 162853916 17908255 416996741 65806774 861867161 105880969 640079448 310744056 21695688 365422238 360704246 227157498 566817594 157655888 945302463 702727889 131418946 192922617 727407642 955096632 589204343 255394260 505912558 669739789 87993396 370347393 857847593 640463825 208808984 714142085 254218813 877498668 127599751 594774727 436532382 928154728 897824294 229240085 79860293 135332337 646718819 99209629 672779568 936159707 415186666 784793972 818195935 782361692 299236913 699420179 144947673 85376077 448650733 901418964 292943909 901510061 20377243 239817337 51767249 987570206 106348280 19896230 953762927 615958886 459470985 805502818 192915603 961763824 887328788 117752474 728146518 818888520 179177509 641325470 240481750 438401187 154425738 204150946 610866100 761688404 39634392 768412223 446609300 366585176 542507492 401746927 820329120 538969035 816890954 600258708 997025286 994668913 179613673 953259249 569632629 299950894 30014564 810405935 835787172 160847502 886801059 340766298 283803852 387862590 692979536 129476834 183006505 419734673 102532443 956132123 290807164 101005308 448714871 832193213 487415692 54554010 880314266 132138084 888337056 924021672 462151553 361950737 416982022 444565002 626469673 740404135 130300304 540074181 930673239 976821103 868050450 528292995 684237841 779442324 901494757 66037522 956699939 550897064 686329191 122899941 6226076 500589341 933531001 315209361 895992910 403686349 3646464 634788689 781284177 927201651 973427812 692943747 910460032 698254640 661746707 54951465 104184570 568269831 357250815 469191273 633841826 238915424 252253212 838926349 31407776 354173321 655748067 473809924 584779230 981095984 249471698 689627359 114429324 770463466 212311018 914328917 790313885 247477168 529559344 173411519 959015752 592548189 279997484 713080733 718614407 807267889 631610477 224418831 796133787 724991569 349523458 44069980 356387206 36883012 928541186 762515823 470500495 730915191 875754758 872040788 772011970 775027386 599031722 665772992 665447022 993899714 495048975 161173639 275245733 710247077 208051548 15789091 479056319 344020064 201569336 265693236 26410711 611720020 237074258 612152315 804215628 148271301 508375258 289167069 684996930 34983514 926177797 147062502 618155551 434570912 580817804 880474435 563742990 380710791 710391341 118363847 710669695 267472099 657605929 22410343 15467941 410945260 777290436 636409790 648681718 330387646 746452681 622298506 594383535 526652122 371989764 348233773 183922254 154236324 100699589 788683820 415154710 697988067 251780195 942352564 645310862 74459971 620215735 485367824 651227138 635840214 661375133 732173876 321848065 838072207 502749815 800570677 12399325 52083910 589863849 992836559 169391918 827320503 770244126 2457566 243193167 849282306 358524353 808271077 372906720 491391276 745004293 444969098 401547330 733832477 875196766 357605655 92420382 268176289 958290374 379476475 537271518 185516263 175609657 44879943 365088563 587261701 802176313 100190002 594557069 889370737 600917066 501226646 11627686 115922057 215592055 921426800 782293240 290463757 909757900 854445155 210990914 140273055 293898457 481562678 96047623 579065930 273067829 919707218 69398286 1737720 674224121 979340613 35121635 84366331 628937281 755139393 232672341 556295045 735038383 700555421 508569846 178127919 747660520 713871443 821563294 4806774 620083220 436887169 939217384 352499769 285705570 78950632 529019828 621699901 715072898 276026224 228796323 496828841 19700777 747461282 249199518 28899466 587284113 294334508 260259664 254946896 633445878 327141217 242249383 217464143 631987226 815305654 385879639 183151167 321345985 740932934 417390167 595043005 260491062 716247887 917964385 521951688 125753541 406287539 542783606 636139076 240134462 801671800 532079449 552201082 725633145 673087561 559788815 896553366 596755916 60557042 478484837 788871208 549464214 758457063 243015274 198572196 216644280 556619966 71482608 494967522 681524503 468210096 864990991 17363358 346113052 909461532 43861667 439852281 184072243 116162565 892607433 122177782 988276815 367889295 619973990 211242494 268150373 727088517 852008864 927950685 201746412 898823126 483676258 535372738 529365091 160491540 200799709 77935555 645228491 64656883 617300738 789916247 514430761 267817424 284253704 361913690 318787334 480106280 820887788 134296588 852021743 170395420 548261356 722046866 586938613 845854452 967409675 930376564 385173549 480285848 631332241 988398109 762170672 737496345 20744840 532594015 604432285 229859622 339950912 700298476 198763923 931072919 200238283 190708446 191402551 196369382 785546626 884274735 574406196 544618673 702178174 168948034 899590198 836298810 615960351 578263129 425191790 177153767 880811913 475526684 621354001 488017346 365372194 419659800 726600153 518238457 751824406 756437309 312573058 190081631 440988371 696449632 591448142 783715818 60439181 247047351 772080770 310656563 539367355 496525920 273920487 197350649 503186072 538485466 731451722 938269598 795551139 954921353 33659388 151769512 851077663 201469494 830963794 441760065 521146004 979497357 480171558 767078840 791309132 16145822 482686292 37902334 424185047 899171933 838829118 575463210 960457351 161507874 848209481 436182774 4772597 363750442 565915742 844664383 820868730 349804308 254047081 612217224 412570551 804759396 463546078 786543480 770364942 535777283 189380399 564506455 463139366 961078973 236797527 59423637 255954026 238862017 980485714 183993412 362796939 647725861 251624354 683535257 711942394 584262496 707123148 617521263 903510895 428237774 520246233 445636291 692107621 617428528 287409878 20559929 258384283 359705129 536394836 921786518 513758612 84327362 331100904 422231107 204021272 468156902 496592044 263019217 699877297 170276583 97865660 240386415 65138991 273708279 547031738 423391606 285615652 699761840 989652299 21531870 531918185 797499789 587719832 211028166 173181847 206540398 545839054 967454192 328784271 673840664 268306590 790155586 726412531 143864243 55715262 903176262 564537002 558577482 948625253 556744618 315466592 598315598 454492627 585860033 628041219 890916372 219475399 978718977 207794759 626458194 13897991 513359491 146622243 827662758 82996444 774082182 603186002 246946831 795427987 723751149 679190484 553218418 14255613 734386620 146399338 668310038 882011119 185086878 383109149 225997608 737935555 718764130 247258039 739240248 341981910 672511354 380169288 425951930 760989448 998793850 121105315 497460871 324064575 49550751 86912222 277387353
688574692 58817094 804183254 731433810 409608548 172527472 297928360 623369846 121886384 34987588 180351033 770782508 73015229 929629325 200275120 481636289 994370309 420705080 983255798 207036901 235005701 837289688 774749757 247798059 671606461 885195810 914657910 801513869 238405171 178737265 773591257 500333543 153710832 546339395 412406881 829697655 771939457 73614265 861395533 815917412 482881783 558062363 327231137 230132020 554974567 923914066 239598243 116339027 922741355 770107501 554331998 478463635 701303456 593504797 96669218 388836775 65705766 793210424 230532866 398261158 977444899 74394937 307688788 119106191 848113472 863235262 101007925 26926015 581872170 343808009 121958659 259226748 9903378 233809536 273113569 448214126 718226734 216168494 371122230 634092576 743237430 935720511 480216878 432792964 167087079 486662536 792378423 419684972 701983876 907998460 899468678 963778322 603297104 11426360 929086608 453941393 795612693 622753272 285170833 452792169 401257120 347625631 788762376 920786943 357284674 583222964 700919353 591550234 620604240 46201695 13335466 956849767 570965412 508576496 363901094 336883959 581792027 905998681 700648637 689793980 724482837 473112239 35775042 135998991 127417336 353730988 689659083 199664685 273043885 293100592 368961973 304459189 786265634 6065084 405525662 658149931 160243654 313194997 614772713 297934713 298405391 295626535 745305917 163999337 541369847 727766207 176894982 745282348 300086907 540793296 867856371 456582614 232787227 334518671 59943286 885818591 978983006 790047191 67667527 855883683 564012619 318529958 862016994 305735395 24309488 738166174 220806660 145733954 979747038 26098821 664357170 277869002 609441195 500283845 128811314 707291236 209799791 697795053 245001615 470229603 309445703 77425454 178261017 897346810 503914198 509342174 141866339 1789889 263896767 477290745 805706564 974298932 807556652 763464859 500747094 760683316 234330442 614960263 71824250 140896132 65380042 816397987 330072658 377894477 960096866 103406970 291854278 874921114 336771914 257632440 937616256 360639709 58817728 454111154 30090607 518296936 860490372 531323868 879661128 766738165 598042460 111590736 279839232 177324831 241810322 781893454 944416851 642492646 634908529 295005878 628636993 696046383 281515979 930520720 151875467 910272834 522292854 938982532 664314170 542163274 113693386 308028258 638436377 598707929 815473701 123791772 100499510 330386273 504283751 918642119 582601317 932356283 980323958 920378654 557195453 676266916 562767035 703191551 757151513 551573051 14834084 969849451 293027736 874568325 820477984 136285834 984344349 851886314 185604646 150164773 12197839 869551285 375647022 762521642 555884442 703058583 458411702 694836524 190979245 278817572 199373502 428374497 614302202 765215060 341497932 624351394 916356538 834688260 173968873 551224558 54306790 370260851 670097443 388432871 64249535 97613253 57912329 485824723 680774982 538794371 835094962 191774620 538167748 118901017 924755638 758153041 572694596 844935767 281419955 667261091 933570324 99803377 539848137 406207593 191160136 172607743 577499935 789917724 193895735 462415742 198468444 948794971 103030524 475208908 179972398 312654697 731382 435779888 640751559 542795690 692921416 520458576 357660506 869837354 380085082 626876600 306675619 830643990 106043478 857376346 280013916 199072320 545275820 653669129 253654985 115326879 350736014 72147452 578251565 580547021 644919156 43268946 909006674 933217927 824914586 881992840 319905030 146775345 881854077 350023428 763197336 745784655 785835618 359740558 80151391 283210509 272852687 885235665 388258355 767764408 18008080 276015327 554977778 263096387 694560435 856928682 379301117 585063875 654678540 313641612 230241464 799185395 359515314 907943104 481158669 405514161 201624320 288175846 955707882 253779327 300260757 648585091 354718654 615937539 752088020 485620606 290337280 343095943 741446757 660238501 211484328 932749178 76175282 333195814 345004468 137938157 945733739 576702230 631461285 30783254 722941443 953173230 100657151 919508688 574031664 454206472 738060748 555502105 606100079 903365670 462917658 249142932 727672957 503286508 371097720 699751429 496002271 724454497 950412157 495015639 962210907 387442546 88137538 866999961 332910973 137973359 829758434 144199804 720965395 711028620 41083905 427144663 490490033 600103778 591215426 959013540 816657710 27828587 312115408 26567680 375118117 80707721 131089878 956839086 737362293 96428927 826659847 188278677 868999106 532012406 883210263 923774526 791081714 750884986 570343999 624933207 946326960 526508027 596681917 820890930 649152236 794341197 661155410 118403142 927412824 346479144 805176002 559978413 199119597 593513256 41411415 300086181 134466916 747420750 316809055 208686607 850314430 276730237 570699945 867449587 953282237 150821630 555619852 529733370 134983272 828099068 521145313 116978674 169066635 966683401 590788228 967158606 987706932 62717079 683149014 311836836 835854647 78768512 17846462 116851757 197386924 750506879 670768035 315446600 520632172 832319925 849489652 145030391 942707863 536455461 855420064 478460512 142441488 565932855 113549726 658316109 491040511 884429881 942825575 447440045 316002382 312982489 990027127 988022545 631268653 498038188 166002639 597050159 128430479 186730923 397752694 423046755 397734570 648790705 917923827 305209129 228194171 785224446 178361045 284957092 441272128 836678839 636013099 904317979 859304956 772223075 786909964 132634998 551182582 828081007 523827729 529247173 751514938 6693035 905299926 296462521 684741142 35452108 218845053 454464553 57818527 705829096 256604458 433453199 198502698 785037053 425246344 938786697 879749587 770384490 788812610 765216856 617174777 535593587 499845003 858332772 232501952 666897089 434678935 122196917 777507469 19493344 831956767 401347452 581805454 645776320 231724001 153571976 756426544 896475189 369616414 420908498 118247335 136056183 322742811 955534066 645030505 27874467 510484384 193753766 558689459 795405367 189091452 357099346 979943427 253556890 511283967 341530491 94219420 54961810 162891902 815171147 991822341 830945739 466293714 778067985 433685898 679490903 902431193 901320381 704907449 55269417 642353140 122652776 344997863 474389401 58889352 457026506 217007273 834453475 458634109 604081858 369090651 73999527 46743234 519461074 197438620 650150250 985114310 461306785 26160080 407047700 682307329 933382519 500272541 355898737 620649 522275268 86019950 953273264 780502525 52485017 814070003 518405863 231319870 194853933 252041887 938100620 330596017 657003353 128585769 585742077 292273246 326380573 239360268 686099450 635083348 690986777 364133638 505244966 341909795 353130260 868286620 250847625 929408096 467843961 864257429 829396240 184155428 423427285 643515771 499765004 628343437 778597723 678297629 531438255 478259260 795451232 446093328 152978322 430533334 129604062 895193897 903126578 783522948 637911285 950938372 255158894 180252018 388405862 136220545 326737419 716641363 359555094 318563137 692716848 579836123 575195281 993426989 151514858 806029892 912360837 712912368 641995689 818243018 859790402 838154872 186772417 381717807 125088833 78866041 571126763 561045816 748365722 468841962 478125505 675117613 308339596 187201669 417852485 827711069 573181689 810363979 545206362 303949976 52846311 686958590 964880201 354844339 567532800 803005862 463533886 51792904 298229779 792792845 89921481 457517555 816903313 606835267 521166942 128078934 195309840 31477786 798386901 118143509 655717580 320441002 39796202 732149659 377653281 127999951 426949054 662699348 354725650 947819430 576902740 626597937 907523525 351470356 897324053 118640679 213775621 120895551 695485517 780966576 263640255 378974482 759184811 374455112 867355781 618479549 244725957 897362417 183672334 296799027 304090258 384671663 618440116 614892971 939189486 82137357 922917108 967371040 716527385 53656215 987691250 639081425 24432184 865678686 153661170 425649345 869043667 845570935 905464544 424832568 998606933 299639932 231750089 933712448 501889424 712270345 337158752 80639273 546445110 443965504 221525370 678476293 37421921 773632070 735330962 87313708 815763724 477383875 996934 189009082 802829463 346964582 174779607 822490380 733719623 473743455 709135533 195041607 945184963 132666084 401332433 480749521 111515032 178251692 406149490 172465366 440866742 211522679 896689761 229204164 794584562 356829572 314958740 748152527 566821762 327307800 273525670 454344558 443668100 525972222 614765653 693496028 701239415 690348802 434316035 144840600 944983743 596008309 798828855 175196901 628840741 656724652 905118489 203450187 98169941 783443585 482635769 167779092 275322463 408181456 192357576 473299152 866759479 630524411 477254301 255548369 271218997 184755559 296329521 745629872 897094038 657650685 156889955 613996486 137167097 657708714 952319926 248354740 14951394 438221535 26075342 422468059 837905210 485283601 743861239 971383525 754719949 286256442 79577502 304933690 279465418 880780118
